package day0401;

import java.util.*;


public class Qujian30 {
    /**
     * 30.区间交集
     * 【区间交集】给定一组闭区间，其中部分区间存在交集。任意两个给定区间的交集，称为公共区间(如:[1,2],[2,3]的公共区间为[2,2]，[3,5],[3,6]的公共区间为
     * [3,5])。公共区间之间 若存在交集，则需要合并(如:[1,3],[3,5]区间存在交集[3,3]，需合并为[1,5])。按升序排列 输出合并后的区间列表。
     * 输入描述: 一组区间列表，区间数为 N: 0<=N<=1000;区间元素为 X: -10000<=X<=10000。
     * 输出描述: 升序排列的合并区间列表
     * 备注:
     * 1、区间元素均为数字，不考虑字母、符号等异常输入。
     * 2、单个区间认定为无公共区间。
     * 示例:
     * 示例 1
     * 输入：
     * 0 3
     * 1 3
     * 3 5
     * 3 6
     * 输出：
     * 1 5
     * 示例 2
     * 输入：
     * 0 3
     * 1 4
     * 4 7
     * 5 8
     * 输出：
     * 1 3
     * 4 4
     * 5 7
     * <p>
     * 示例 3
     * 输入：
     * 1 2
     * 3 4
     * 输出：
     * None
     */
    private static boolean flag = false;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ArrayList<int[]> list = new ArrayList<>();
        while (sc.hasNextLine()) {
            String ss = sc.nextLine();
            if (ss.isEmpty()) {
                break;
            }
            String[] s = ss.split(" ");
            int[] num = new int[2];
            num[0] = Integer.parseInt(s[0]);
            num[1] = Integer.parseInt(s[1]);
            list.add(num);
        }
        list.sort((o1, o2) -> o1[0] - o2[0]);
        // 交集
        ArrayList<int[]> jjList = new ArrayList<>();
        for (int i = 0; i < list.size() - 1; i++) {
            if (list.get(i)[1] >= list.get(i + 1)[0] && list.get(i)[1] <= list.get(i + 1)[1]) {
                int[] num = new int[2];
                num[0] = list.get(i + 1)[0];
                num[1] = list.get(i)[1];
                jjList.add(num);
            }
        }
        // 交集的并集
        jjList = extracted(jjList);
        if (flag) {
            jjList = extracted(jjList);
        }

        if (jjList.isEmpty()) {
            System.out.println("None");
        } else {
            for (int[] ints : jjList) {
                System.out.println(ints[0] + " " + ints[1]);
            }
        }


    }

    private static ArrayList<int[]> extracted(ArrayList<int[]> jjList) {
        ArrayList<int[]> bjList = new ArrayList<>();
        for (int i = 0; i < jjList.size() - 1; i++) {
            if (jjList.get(i)[1] >= jjList.get(i + 1)[0] && jjList.get(i)[1] <= jjList.get(i + 1)[1]) {
                int[] num = new int[2];
                num[0] = jjList.get(i)[0];
                num[1] = jjList.get(i + 1)[1];
                bjList.add(num);
                flag = true;
            } else {
                if (i == jjList.size() - 2) {
                    bjList.add(jjList.get(i));
                    bjList.add(jjList.get(i + 1));

                } else {
                    bjList.add(jjList.get(i));
                }
            }
        }
        return bjList;
    }
}

